package com.cwj.algorithm.graph;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author chenwujie
 * @date 2020-12-22 15:30
 */
public class DepthFirstPaths {
    /**
     * 图
     */
    private Graph graph;
    /**
     * 已搜索顶点
     */
    private boolean[] marked;
    /**
     * 起点
     */
    private int start;
    /**
     * 路径上的顶点的前置顶点
     */
    private int[] edgeTo;

    public DepthFirstPaths(Graph graph, int start) {
        this.graph = graph;
        this.marked = new boolean[graph.getV()];
        this.start = start;
        this.edgeTo = new int[graph.getV()];
        Arrays.fill(edgeTo, -1);
    }

    public void dfs() {
        dfs(start);
    }

    private void dfs(int v) {
        marked[v] = true;
        Deque<Integer> vertexes = graph.getVertexes(v);
        for (Integer vertex : vertexes) {
            if (!marked[vertex]) {
                edgeTo[vertex] = v;
                dfs(vertex);
            }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Deque<Integer> pathTo(int v) {
        Deque<Integer> stack = new LinkedList<>();
        if (hasPathTo(v)) {
            int i = v;
            while (i != start){
                stack.push(i);
                i = edgeTo[i];
            }
            stack.push(start);
        }
        return stack;
    }
}
